#include "helpers.cpp"

#include <stdlib.h>

#include <NTL/LLL.h>
#include <NTL/vector.h>

#include <time.h>
#include <algorithm>
#include <queue>

#define LIST_THRESHOLD basis.NumCols()
#define RANDOM_THRESHOLD basis.NumCols()
#define GAUSS_THRESHOLD basis.NumCols() 


NTL_CLIENT

void help();

void sorted_add(vec *t, vector<vec> &list);

vec list_sieve(mat_ZZ basis);
void list_reduce(vec *t, vector<vec> &list);

double pi = atan(1) * 4;

int DIM;

int main(int argc, char** argv)
{
  srand(time(0));

  if(argc != 4)
    help();

  for(int i = atoi(argv[1]); i <= atoi(argv[2]); i++) 
  {
    for(int j = 0; j < atoi(argv[3]); j++)
    {
      DIM = i;
      mat_ZZ basis = randomBasis(i);
      mat_ZZ LLL_basis = basis;
      G_BKZ_FP(basis, 0.99, 20);

      //some useful stats to keep track of
      ZZ shortest_mag_sq; 

      //uses LLL to find shortest vector! 
      ZZ det;
      long i = LLL(det, LLL_basis);
      //set shortest mag square so we can compare to what we got
      shortest_mag_sq =  mag_sq(LLL_basis[LLL_basis.NumRows() - i]);

      //do list sieve algorthim
      vec l = list_sieve(basis);

      //compare the vectors
      cout << (l.mag_sq <= shortest_mag_sq) << endl;
    }
  }

  return 0;
}

/*
 * list sieve finds the shortest vector by getting a random lattice vector 
 * which is obtained by multiplying the basis vectors by either 0 or 1 and then
 * reducing the random lattice vector as much as possible using vectors from 
 * our list
 */
vec list_sieve(mat_ZZ basis)
{
  vector<vec> list;
  int collisions = 0;
  vec t;
  //while we haven't hit threshold number of collisions
  while(collisions < LIST_THRESHOLD)
  {
    //get a random lattice vector
    t = randomVec(basis);
    //reduce it using vectors from initially empty list
    list_reduce(&t, list);
    if(t.mag_sq == 0)
      //if we get a collision increment collisions
      collisions++;
    else
      //if not a collision we add it to the list, keeping the list sorted
      sorted_add(&t, list);
  }

  return list[0];
}

/* 
 * reduces t using vectors in the list, which we assume to be sorted
 * We stop when we reach the end of the list or when we reach a vector that is
 * longer than t. Also, whenever we reduce t we start again.
 */
void list_reduce(vec *t, vector<vec> &list)
{
  for(int i = 0; i < list.size(); i++)
  {
    //if the list vector is longer we are done!
    if(list[i].mag_sq > t->mag_sq)
      break;
    vec red = reduce(t, &list[i]);
    if(red.mag_sq < t->mag_sq)
    {
      *t = red;
      i = 0;
    }
  }
}

/* 
 * This function needs to add the vec to the list in a way such that the 
 * list remains sorted, and we can assume it is already sorted
 */
void sorted_add(vec *t, vector<vec> &list)
{
  //we start from the top since it's more likely that we will add a short one
  //just increments i till we are at a point that t is shorter than list[i]
  int i = 0;
  while(i < list.size() && list[i].mag_sq < t->mag_sq)
    i++;

  list.insert(list.begin() + i, *t);;
}




void help()
{
  cout << "Please give three integer arguments corresponding to what\n" 
      << "dimension you want to start and end at, inclusive, and how many\n"
      << "times you want to run the algorithm at each dimension\n";
  exit(0);
}
